package suanfa;

import java.util.*;

/**
 *  给定2个大小为m和n的有序数组，找出这2个数组的中位数
 *  要求算法的复杂度为O(log(m+n))
 *  可以假设两个数组不同时为空
 */
public class MidelNumbers
{
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        double midel = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums1.length; i++)
        {
            set.add(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++)
        {
            set.add(nums2[i]);
        }

        List<Integer> list = new ArrayList(set);
        Collections.sort(list);
        if (set.size() % 2 != 0)
        {
            midel = Double.valueOf(list.get((set.size())/2));
            return midel;
        }
        midel = Double.valueOf((list.get((set.size())/2)+list.get((set.size())/2-1)))/2;
        return midel;
    }

    public static void main(String[] args)
    {
        MidelNumbers midelNumbers = new MidelNumbers();

        int[] a = {3};
        int[] b = {-1,-2};
        double medianSortedArrays = midelNumbers.findMedianSortedArrays(a, b);
        System.out.println(medianSortedArrays);
    }
}
